import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * user:likai
 * Date:2022-10-19
 * Time:8:24
*/

//栈实现队列
class MyQueue {
    Stack<Integer> s1;
    Stack<Integer> s2;
    public MyQueue() {
        //入
        s1=new Stack<>();
        //出
        s2=new Stack<>();
    }
    public void push(int x) {
        s1.push(x);
    }

    public int pop() {
        if(empty()){
            return -1;
        }
        if(s2.empty()){
            int sum=s1.size();
            for (int i = 0; i < sum; i++) {
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }

    public int peek() {
        if(empty()){
            return -1;
        }
        if(s2.empty()){
            int sum=s1.size();
            for (int i = 0; i < sum; i++) {
                s2.push(s1.pop());
            }
        }
        return s2.peek();

    }

    public boolean empty() {
        return s1.empty()&&s2.empty();
    }
}


//队列实现栈
class MyStack1 {
    public Queue<Integer> q1;
    public Queue<Integer> q2;
    public MyStack1() {
        q1=new LinkedList<>();
        q2=new LinkedList<>();
    }

    public void push(int x) {
        if(!q1.isEmpty()){
            q1.offer(x);
        } else if (!q2.isEmpty()) {
            q2.offer(x);
        }else {
            q1.offer(x);
        }
    }

    public int pop() {
        if(empty()){
            return -1;
        }
        if(q1.isEmpty()){
            int sum=q2.size();
            for (int i = 0; i < sum-1; i++) {
                q1.offer(q2.poll());
            }
            return q2.poll();
        }else {
            int sum = q1.size();
            for (int i = 0; i < sum - 1; i++) {
                q2.offer(q1.poll());
            }
            return q1.poll();
        }
    }

    public int top() {
        if(empty()){
            return -1;
        }
        if(q1.isEmpty()){
            int sum=q2.size();
            for (int i = 0; i < sum-1; i++) {
                q1.offer(q2.poll());
            }
            int ret=q2.peek();
            q1.offer(q2.poll());
            return ret;
        }else{
            int sum=q1.size();
            for (int i = 0; i < sum-1; i++) {
                q2.offer(q1.poll());
            }
            int ret=q1.peek();
            q2.offer(q1.poll());
            return ret;
        }
    }

    public boolean empty() {
        return q1.isEmpty()&&q2.isEmpty();
    }
}

class MyCircularQueue {

    private int []elem;
    public int front;
    public int tail;

    public MyCircularQueue(int k) {
        elem=new int[k+1];
    }

    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }else {
            elem[tail]=value;
            tail=(tail+1)%elem.length;
            return true;
        }

    }

    public boolean deQueue() {
        if(isEmpty()){
            return false;
        }else{
            front=(front+1)%elem.length;
            return true;
        }
    }

    public int Front() {
        if(isEmpty()){
            return -1;
        }
        return elem[front];
    }

    public int Rear() {
        if(isEmpty()){
            return -1;
        }
        if(tail==0){
            return elem[elem.length-1];
        }else{
            return elem[tail-1];
        }
    }

    public boolean isEmpty() {
        if(front==tail){
            return true;
        }else {
            return false;
        }
    }

    public boolean isFull() {
        //浪费空间
        if((tail+1)%elem.length==front){
            return true;
        }
        return false;
    }
}

class MinStack {
    public Stack<Integer> s1;
    public Stack<Integer> s2;
    public MinStack() {
        s1=new Stack<>();
        s2=new Stack<>();
    }
    public void push(int val) {
        if(s1.empty()&&s2.empty()){
            s1.push(val);
            s2.push(val);
        }else {
            s1.push(val);
            if(s2.peek()>=val){
                s2.push(val);
            }
        }
    }

    public void pop() {
        if(s1.empty()&&s2.empty()){
            return;
        }else {
            if(s1.peek().equals(s2.peek())){
                s1.pop();
                s2.pop();
            }else {
                s1.pop();
            }
        }
    }

    public int top() {
        if(s1.empty()){
            return -1;
        }
        return s1.peek();
    }

    public int getMin() {
        if(s2.empty()){
            return -1;
        }
        return s2.peek();
    }
}

public class Test {
    public static boolean isValid(String s) {
        Stack<Character> stack=new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char a=s.charAt(i);
            if(a=='('||a=='['||a=='{'){
                stack.push(a);
            }else {
                //左括号多
                if(stack.empty()){
                    return false;
                }else {
                    //不匹配
                    char b=stack.peek();
                    if(b=='('&&a==')'||b=='['&&a==']'||b=='{'&&a=='}'){
                        stack.pop();
                    }else {
                        return false;
                    }
                }
            }
        }
        //右括号多
        if(stack.empty()){
            return true;
        }else {
            return false;
        }
    }
    //出栈入栈次序匹配
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> stack=new Stack<>();
        int j=0;
        for (int i = 0; i < pushA.length; i++) {
            stack.push(pushA[i]);
            //Interge的范围是-127~128，所以不能用等于
            //while(!stack.empty()&&stack.peek()==popA[j]){
            while(!stack.empty()&&stack.peek().equals(popA[j])){
                stack.pop();
                j++;
            }
        }
        if(j==popA.length&&!stack.empty()){
            return true;
        }else {
            return false;
        }
    }
    public static void main1(String[] args) {
        String s="()";
        System.out.println(isValid(s));
    }

    public static void main(String[] args) {
//        MyQueue myQueue=new MyQueue();
//        myQueue.push(1);
//        myQueue.push(2);
//        System.out.println(myQueue.peek());
//        System.out.println(myQueue.pop());
        MinStack minStack =new MinStack();
        minStack.push(512);
        minStack.push(-213);
        minStack.push(-213);
        minStack.push(512);
        minStack.pop();
        System.out.println(minStack.getMin());
        minStack.pop();
        System.out.println(minStack.getMin());
        minStack.pop();
        System.out.println(minStack.getMin());
    }
}
